package array;

/**
 * create by yctc
 **/

/**
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 * 示例:
 *
 * 输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 *
 * 说明:
 *
 * 必须在原数组上操作，不能拷贝额外的数组。
 * 尽量减少操作次数。
 */
public class MoveZero {
    public static void main(String[] args) {
        int nums[] = {0, 1, 0, 3, 12};
        moveZeroes0(nums);
        moveZeroes1(nums);
        moveZeroes2(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]);
            if (i < nums.length - 1) {
                System.out.print(",");
            }
        }
    }

    /**
     * 简单双指针
     */
    public static void moveZeroes0(int[] nums) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            // 只要不为零，就将该数字往前移动
            if (nums[j] != 0) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
            }
        }
    }

    /**
     * 进阶双指针
     */
    public static void moveZeroes1(int[] nums) {
        int i = 0; // 统计 0 的个数
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == 0) {
                i++;
            } else if (i != 0) {
                //把当前数字放到最前面那个0的位置，然后再把
                //当前位置设为0
                nums[j - i] = nums[j];
                nums[j] = 0;
            }
        }
    }

    /**
     * 一次操作
     */
    public static void moveZeroes2(int[] nums) {
        if (nums.length < 1) {
            return;
        }
        int index = 0;
        for (int j = 0; j < nums.length; j++) {
            // 非0数全部往前移动
            if (nums[j] != 0) {
                nums[index++] = nums[j];
            }
        }

        // 将后面数全部置为0
        while (index < nums.length) {
            nums[index++] = 0;
        }
    }
}
